package data_structures_and_algorithms.tree;

import common.TreeNode;

/**
 * @ClassName Code_0104_maxDepth
 * @Description: https://leetcode.cn/problems/minimum-depth-of-binary-tree/
 * @Author: yongliang.ma
 * @Create_time:2022/10/26 20:59
 */
public class Code_0111_minDepth {



    public static class FromUpToBottom{
        public int minDepth(TreeNode root) {
            if (root == null)
                return 0;

            return dfs(root, 0);
        }

        public int dfs(TreeNode root, int depth){
            // 满足叶子条件 返回
            if (root.left == null && root.right == null)
                return depth + 1;

            int leftDepth = root.left == null?Integer.MAX_VALUE : dfs(root.left, depth + 1);
            int rightDepth = root.right == null ? Integer.MAX_VALUE : dfs(root.right, depth + 1);

            return Math.min(leftDepth, rightDepth);
        }

    }

    public static class FromBottomToUp{
        public int minDepth(TreeNode root) {
            if (root == null)
                return 0;

            return dfs(root);
        }

        public int dfs(TreeNode root){
            if (root.left == null && root.right == null)
                return 1;

            int leftDepth = root.left == null?Integer.MAX_VALUE : dfs(root.left) + 1;
            int rightDepth = root.right == null ? Integer.MAX_VALUE : dfs(root.right) + 1;

            return Math.min(leftDepth, rightDepth);
        }
    }



}
